TFL/rules.ML
changeset 22596 d0d2af4db18f
parent 21858 05f57309170c
equal deleted inserted replaced
22595:293934e41dfd 22596:d0d2af4db18f
   169 
   169 
   170 
   170 
   171 (*----------------------------------------------------------------------------
   171 (*----------------------------------------------------------------------------
   172  *        Disjunction
   172  *        Disjunction
   173  *---------------------------------------------------------------------------*)
   173  *---------------------------------------------------------------------------*)
   174 local val {prop,sign,...} = rep_thm disjI1
   174 local val {prop,thy,...} = rep_thm disjI1
   175       val [P,Q] = term_vars prop
   175       val [P,Q] = term_vars prop
   176       val disj1 = Thm.forall_intr (Thm.cterm_of sign Q) disjI1
   176       val disj1 = Thm.forall_intr (Thm.cterm_of thy Q) disjI1
   177 in
   177 in
   178 fun DISJ1 thm tm = thm RS (forall_elim (D.drop_prop tm) disj1)
   178 fun DISJ1 thm tm = thm RS (forall_elim (D.drop_prop tm) disj1)
   179   handle THM (msg, _, _) => raise RULES_ERR "DISJ1" msg;
   179   handle THM (msg, _, _) => raise RULES_ERR "DISJ1" msg;
   180 end;
   180 end;
   181 
   181 
   182 local val {prop,sign,...} = rep_thm disjI2
   182 local val {prop,thy,...} = rep_thm disjI2
   183       val [P,Q] = term_vars prop
   183       val [P,Q] = term_vars prop
   184       val disj2 = Thm.forall_intr (Thm.cterm_of sign P) disjI2
   184       val disj2 = Thm.forall_intr (Thm.cterm_of thy P) disjI2
   185 in
   185 in
   186 fun DISJ2 tm thm = thm RS (forall_elim (D.drop_prop tm) disj2)
   186 fun DISJ2 tm thm = thm RS (forall_elim (D.drop_prop tm) disj2)
   187   handle THM (msg, _, _) => raise RULES_ERR "DISJ2" msg;
   187   handle THM (msg, _, _) => raise RULES_ERR "DISJ2" msg;
   188 end;
   188 end;
   189 
   189 
   272 
   272 
   273 (*----------------------------------------------------------------------------
   273 (*----------------------------------------------------------------------------
   274  *        Universals
   274  *        Universals
   275  *---------------------------------------------------------------------------*)
   275  *---------------------------------------------------------------------------*)
   276 local (* this is fragile *)
   276 local (* this is fragile *)
   277       val {prop,sign,...} = rep_thm spec
   277       val {prop,thy,...} = rep_thm spec
   278       val x = hd (tl (term_vars prop))
   278       val x = hd (tl (term_vars prop))
   279       val cTV = ctyp_of sign (type_of x)
   279       val cTV = ctyp_of thy (type_of x)
   280       val gspec = forall_intr (cterm_of sign x) spec
   280       val gspec = forall_intr (cterm_of thy x) spec
   281 in
   281 in
   282 fun SPEC tm thm =
   282 fun SPEC tm thm =
   283    let val {sign,T,...} = rep_cterm tm
   283    let val {thy,T,...} = rep_cterm tm
   284        val gspec' = instantiate ([(cTV, ctyp_of sign T)], []) gspec
   284        val gspec' = instantiate ([(cTV, ctyp_of thy T)], []) gspec
   285    in
   285    in
   286       thm RS (forall_elim tm gspec')
   286       thm RS (forall_elim tm gspec')
   287    end
   287    end
   288 end;
   288 end;
   289 
   289 
   291 
   291 
   292 val ISPEC = SPEC
   292 val ISPEC = SPEC
   293 val ISPECL = fold ISPEC;
   293 val ISPECL = fold ISPEC;
   294 
   294 
   295 (* Not optimized! Too complicated. *)
   295 (* Not optimized! Too complicated. *)
   296 local val {prop,sign,...} = rep_thm allI
   296 local val {prop,thy,...} = rep_thm allI
   297       val [P] = add_term_vars (prop, [])
   297       val [P] = add_term_vars (prop, [])
   298       fun cty_theta s = map (fn (i, (S, ty)) => (ctyp_of s (TVar (i, S)), ctyp_of s ty))
   298       fun cty_theta s = map (fn (i, (S, ty)) => (ctyp_of s (TVar (i, S)), ctyp_of s ty))
   299       fun ctm_theta s = map (fn (i, (_, tm2)) =>
   299       fun ctm_theta s = map (fn (i, (_, tm2)) =>
   300                              let val ctm2 = cterm_of s tm2
   300                              let val ctm2 = cterm_of s tm2
   301                              in (cterm_of s (Var(i,#T(rep_cterm ctm2))), ctm2)
   301                              in (cterm_of s (Var(i,#T(rep_cterm ctm2))), ctm2)
   304         (cty_theta s (Vartab.dest ty_theta),
   304         (cty_theta s (Vartab.dest ty_theta),
   305          ctm_theta s (Vartab.dest tm_theta))
   305          ctm_theta s (Vartab.dest tm_theta))
   306 in
   306 in
   307 fun GEN v th =
   307 fun GEN v th =
   308    let val gth = forall_intr v th
   308    let val gth = forall_intr v th
   309        val {prop=Const("all",_)$Abs(x,ty,rst),sign,...} = rep_thm gth
   309        val {prop=Const("all",_)$Abs(x,ty,rst),thy,...} = rep_thm gth
   310        val P' = Abs(x,ty, HOLogic.dest_Trueprop rst)  (* get rid of trueprop *)
   310        val P' = Abs(x,ty, HOLogic.dest_Trueprop rst)  (* get rid of trueprop *)
   311        val theta = Pattern.match sign (P,P') (Vartab.empty, Vartab.empty);
   311        val theta = Pattern.match thy (P,P') (Vartab.empty, Vartab.empty);
   312        val allI2 = instantiate (certify sign theta) allI
   312        val allI2 = instantiate (certify thy theta) allI
   313        val thm = Thm.implies_elim allI2 gth
   313        val thm = Thm.implies_elim allI2 gth
   314        val {prop = tp $ (A $ Abs(_,_,M)),sign,...} = rep_thm thm
   314        val {prop = tp $ (A $ Abs(_,_,M)),thy,...} = rep_thm thm
   315        val prop' = tp $ (A $ Abs(x,ty,M))
   315        val prop' = tp $ (A $ Abs(x,ty,M))
   316    in ALPHA thm (cterm_of sign prop')
   316    in ALPHA thm (cterm_of thy prop')
   317    end
   317    end
   318 end;
   318 end;
   319 
   319 
   320 val GENL = fold_rev GEN;
   320 val GENL = fold_rev GEN;
   321 
   321 
   322 fun GEN_ALL thm =
   322 fun GEN_ALL thm =
   323    let val {prop,sign,...} = rep_thm thm
   323    let val {prop,thy,...} = rep_thm thm
   324        val tycheck = cterm_of sign
   324        val tycheck = cterm_of thy
   325        val vlist = map tycheck (add_term_vars (prop, []))
   325        val vlist = map tycheck (add_term_vars (prop, []))
   326   in GENL vlist thm
   326   in GENL vlist thm
   327   end;
   327   end;
   328 
   328 
   329 
   329 
   350 
   350 
   351 fun CHOOSE (fvar, exth) fact =
   351 fun CHOOSE (fvar, exth) fact =
   352   let
   352   let
   353     val lam = #2 (D.dest_comb (D.drop_prop (cconcl exth)))
   353     val lam = #2 (D.dest_comb (D.drop_prop (cconcl exth)))
   354     val redex = D.capply lam fvar
   354     val redex = D.capply lam fvar
   355     val {sign, t = t$u,...} = Thm.rep_cterm redex
   355     val {thy, t = t$u,...} = Thm.rep_cterm redex
   356     val residue = Thm.cterm_of sign (Term.betapply (t, u))
   356     val residue = Thm.cterm_of thy (Term.betapply (t, u))
   357   in
   357   in
   358     GEN fvar (DISCH residue fact) RS (exth RS Thms.choose_thm)
   358     GEN fvar (DISCH residue fact) RS (exth RS Thms.choose_thm)
   359       handle THM (msg, _, _) => raise RULES_ERR "CHOOSE" msg
   359       handle THM (msg, _, _) => raise RULES_ERR "CHOOSE" msg
   360   end;
   360   end;
   361 
   361 
   362 local val {prop,sign,...} = rep_thm exI
   362 local val {prop,thy,...} = rep_thm exI
   363       val [P,x] = term_vars prop
   363       val [P,x] = term_vars prop
   364 in
   364 in
   365 fun EXISTS (template,witness) thm =
   365 fun EXISTS (template,witness) thm =
   366    let val {prop,sign,...} = rep_thm thm
   366    let val {prop,thy,...} = rep_thm thm
   367        val P' = cterm_of sign P
   367        val P' = cterm_of thy P
   368        val x' = cterm_of sign x
   368        val x' = cterm_of thy x
   369        val abstr = #2 (D.dest_comb template)
   369        val abstr = #2 (D.dest_comb template)
   370    in
   370    in
   371    thm RS (cterm_instantiate[(P',abstr), (x',witness)] exI)
   371    thm RS (cterm_instantiate[(P',abstr), (x',witness)] exI)
   372      handle THM (msg, _, _) => raise RULES_ERR "EXISTS" msg
   372      handle THM (msg, _, _) => raise RULES_ERR "EXISTS" msg
   373    end
   373    end
   394  *
   394  *
   395  *---------------------------------------------------------------------------*)
   395  *---------------------------------------------------------------------------*)
   396 (* Could be improved, but needs "subst_free" for certified terms *)
   396 (* Could be improved, but needs "subst_free" for certified terms *)
   397 
   397 
   398 fun IT_EXISTS blist th =
   398 fun IT_EXISTS blist th =
   399    let val {sign,...} = rep_thm th
   399    let val {thy,...} = rep_thm th
   400        val tych = cterm_of sign
   400        val tych = cterm_of thy
   401        val detype = #t o rep_cterm
   401        val detype = #t o rep_cterm
   402        val blist' = map (fn (x,y) => (detype x, detype y)) blist
   402        val blist' = map (fn (x,y) => (detype x, detype y)) blist
   403        fun ex v M  = cterm_of sign (S.mk_exists{Bvar=v,Body = M})
   403        fun ex v M  = cterm_of thy (S.mk_exists{Bvar=v,Body = M})
   404 
   404 
   405   in
   405   in
   406   fold_rev (fn (b as (r1,r2)) => fn thm =>
   406   fold_rev (fn (b as (r1,r2)) => fn thm =>
   407         EXISTS(ex r2 (subst_free [b]
   407         EXISTS(ex r2 (subst_free [b]
   408                    (HOLogic.dest_Trueprop(#prop(rep_thm thm)))), tych r1)
   408                    (HOLogic.dest_Trueprop(#prop(rep_thm thm)))), tych r1)
   411   end;
   411   end;
   412 
   412 
   413 (*---------------------------------------------------------------------------
   413 (*---------------------------------------------------------------------------
   414  *  Faster version, that fails for some as yet unknown reason
   414  *  Faster version, that fails for some as yet unknown reason
   415  * fun IT_EXISTS blist th =
   415  * fun IT_EXISTS blist th =
   416  *    let val {sign,...} = rep_thm th
   416  *    let val {thy,...} = rep_thm th
   417  *        val tych = cterm_of sign
   417  *        val tych = cterm_of thy
   418  *        fun detype (x,y) = ((#t o rep_cterm) x, (#t o rep_cterm) y)
   418  *        fun detype (x,y) = ((#t o rep_cterm) x, (#t o rep_cterm) y)
   419  *   in
   419  *   in
   420  *  fold (fn (b as (r1,r2), thm) =>
   420  *  fold (fn (b as (r1,r2), thm) =>
   421  *  EXISTS(D.mk_exists(r2, tych(subst_free[detype b](#t(rep_cterm(cconcl thm))))),
   421  *  EXISTS(D.mk_exists(r2, tych(subst_free[detype b](#t(rep_cterm(cconcl thm))))),
   422  *           r1) thm)  blist th
   422  *           r1) thm)  blist th
   519             handle TERM _ => get (rst, n+1, L)
   519             handle TERM _ => get (rst, n+1, L)
   520               | U.ERR _ => get (rst, n+1, L);
   520               | U.ERR _ => get (rst, n+1, L);
   521 
   521 
   522 (* Note: rename_params_rule counts from 1, not 0 *)
   522 (* Note: rename_params_rule counts from 1, not 0 *)
   523 fun rename thm =
   523 fun rename thm =
   524   let val {prop,sign,...} = rep_thm thm
   524   let val {prop,thy,...} = rep_thm thm
   525       val tych = cterm_of sign
   525       val tych = cterm_of thy
   526       val ants = Logic.strip_imp_prems prop
   526       val ants = Logic.strip_imp_prems prop
   527       val news = get (ants,1,[])
   527       val news = get (ants,1,[])
   528   in
   528   in
   529   fold rename_params_rule news thm
   529   fold rename_params_rule news thm
   530   end;
   530   end;
   679              val dummy = say "cong rule:"
   679              val dummy = say "cong rule:"
   680              val dummy = say (string_of_thm thm)
   680              val dummy = say (string_of_thm thm)
   681              val dummy = thm_ref := (thm :: !thm_ref)
   681              val dummy = thm_ref := (thm :: !thm_ref)
   682              val dummy = ss_ref := (ss :: !ss_ref)
   682              val dummy = ss_ref := (ss :: !ss_ref)
   683              (* Unquantified eliminate *)
   683              (* Unquantified eliminate *)
   684              fun uq_eliminate (thm,imp,sign) =
   684              fun uq_eliminate (thm,imp,thy) =
   685                  let val tych = cterm_of sign
   685                  let val tych = cterm_of thy
   686                      val dummy = print_cterms "To eliminate:" [tych imp]
   686                      val dummy = print_cterms "To eliminate:" [tych imp]
   687                      val ants = map tych (Logic.strip_imp_prems imp)
   687                      val ants = map tych (Logic.strip_imp_prems imp)
   688                      val eq = Logic.strip_imp_concl imp
   688                      val eq = Logic.strip_imp_concl imp
   689                      val lhs = tych(get_lhs eq)
   689                      val lhs = tych(get_lhs eq)
   690                      val ss' = MetaSimplifier.add_prems (map ASSUME ants) ss
   690                      val ss' = MetaSimplifier.add_prems (map ASSUME ants) ss
   694                      val lhs_eq_lhs2 = implies_intr_list ants lhs_eq_lhs1
   694                      val lhs_eq_lhs2 = implies_intr_list ants lhs_eq_lhs1
   695                      val lhs_eeq_lhs2 = lhs_eq_lhs2 RS meta_eq_to_obj_eq
   695                      val lhs_eeq_lhs2 = lhs_eq_lhs2 RS meta_eq_to_obj_eq
   696                   in
   696                   in
   697                   lhs_eeq_lhs2 COMP thm
   697                   lhs_eeq_lhs2 COMP thm
   698                   end
   698                   end
   699              fun pq_eliminate (thm,sign,vlist,imp_body,lhs_eq) =
   699              fun pq_eliminate (thm,thy,vlist,imp_body,lhs_eq) =
   700               let val ((vstrl, _, used'), args) = dest_pbeta_redex used lhs_eq (length vlist)
   700               let val ((vstrl, _, used'), args) = dest_pbeta_redex used lhs_eq (length vlist)
   701                   val dummy = forall (op aconv) (ListPair.zip (vlist, args))
   701                   val dummy = forall (op aconv) (ListPair.zip (vlist, args))
   702                     orelse error "assertion failed in CONTEXT_REWRITE_RULE"
   702                     orelse error "assertion failed in CONTEXT_REWRITE_RULE"
   703                   val imp_body1 = subst_free (ListPair.zip (args, vstrl))
   703                   val imp_body1 = subst_free (ListPair.zip (args, vstrl))
   704                                              imp_body
   704                                              imp_body
   705                   val tych = cterm_of sign
   705                   val tych = cterm_of thy
   706                   val ants1 = map tych (Logic.strip_imp_prems imp_body1)
   706                   val ants1 = map tych (Logic.strip_imp_prems imp_body1)
   707                   val eq1 = Logic.strip_imp_concl imp_body1
   707                   val eq1 = Logic.strip_imp_concl imp_body1
   708                   val Q = get_lhs eq1
   708                   val Q = get_lhs eq1
   709                   val QeqQ1 = pbeta_reduce (tych Q)
   709                   val QeqQ1 = pbeta_reduce (tych Q)
   710                   val Q1 = #2(D.dest_eq(cconcl QeqQ1))
   710                   val Q1 = #2(D.dest_eq(cconcl QeqQ1))
   723                   val impth1 = impth RS meta_eq_to_obj_eq
   723                   val impth1 = impth RS meta_eq_to_obj_eq
   724                   (* Need to abstract *)
   724                   (* Need to abstract *)
   725                   val ant_th = U.itlist2 (PGEN tych) args vstrl impth1
   725                   val ant_th = U.itlist2 (PGEN tych) args vstrl impth1
   726               in ant_th COMP thm
   726               in ant_th COMP thm
   727               end
   727               end
   728              fun q_eliminate (thm,imp,sign) =
   728              fun q_eliminate (thm,imp,thy) =
   729               let val (vlist, imp_body, used') = strip_all used imp
   729               let val (vlist, imp_body, used') = strip_all used imp
   730                   val (ants,Q) = dest_impl imp_body
   730                   val (ants,Q) = dest_impl imp_body
   731               in if (pbeta_redex Q) (length vlist)
   731               in if (pbeta_redex Q) (length vlist)
   732                  then pq_eliminate (thm,sign,vlist,imp_body,Q)
   732                  then pq_eliminate (thm,thy,vlist,imp_body,Q)
   733                  else
   733                  else
   734                  let val tych = cterm_of sign
   734                  let val tych = cterm_of thy
   735                      val ants1 = map tych ants
   735                      val ants1 = map tych ants
   736                      val ss' = MetaSimplifier.add_prems (map ASSUME ants1) ss
   736                      val ss' = MetaSimplifier.add_prems (map ASSUME ants1) ss
   737                      val Q_eeq_Q1 = MetaSimplifier.rewrite_cterm
   737                      val Q_eeq_Q1 = MetaSimplifier.rewrite_cterm
   738                         (false,true,false) (prover used') ss' (tych Q)
   738                         (false,true,false) (prover used') ss' (tych Q)
   739                       handle U.ERR _ => Thm.reflexive (tych Q)
   739                       handle U.ERR _ => Thm.reflexive (tych Q)
   744                  ant_th COMP thm
   744                  ant_th COMP thm
   745               end end
   745               end end
   746 
   746 
   747              fun eliminate thm =
   747              fun eliminate thm =
   748                case (rep_thm thm)
   748                case (rep_thm thm)
   749                of {prop = (Const("==>",_) $ imp $ _), sign, ...} =>
   749                of {prop = (Const("==>",_) $ imp $ _), thy, ...} =>
   750                    eliminate
   750                    eliminate
   751                     (if not(is_all imp)
   751                     (if not(is_all imp)
   752                      then uq_eliminate (thm,imp,sign)
   752                      then uq_eliminate (thm,imp,thy)
   753                      else q_eliminate (thm,imp,sign))
   753                      else q_eliminate (thm,imp,thy))
   754                             (* Assume that the leading constant is ==,   *)
   754                             (* Assume that the leading constant is ==,   *)
   755                 | _ => thm  (* if it is not a ==>                        *)
   755                 | _ => thm  (* if it is not a ==>                        *)
   756          in SOME(eliminate (rename thm)) end
   756          in SOME(eliminate (rename thm)) end
   757          handle U.ERR _ => NONE    (* FIXME handle THM as well?? *)
   757          handle U.ERR _ => NONE    (* FIXME handle THM as well?? *)
   758 
   758 
   759         fun restrict_prover ss thm =
   759         fun restrict_prover ss thm =
   760           let val dummy = say "restrict_prover:"
   760           let val dummy = say "restrict_prover:"
   761               val cntxt = rev(MetaSimplifier.prems_of_ss ss)
   761               val cntxt = rev(MetaSimplifier.prems_of_ss ss)
   762               val dummy = print_thms "cntxt:" cntxt
   762               val dummy = print_thms "cntxt:" cntxt
   763               val {prop = Const("==>",_) $ (Const("Trueprop",_) $ A) $ _,
   763               val {prop = Const("==>",_) $ (Const("Trueprop",_) $ A) $ _,
   764                    sign,...} = rep_thm thm
   764                    thy,...} = rep_thm thm
   765               fun genl tm = let val vlist = subtract (op aconv) globals
   765               fun genl tm = let val vlist = subtract (op aconv) globals
   766                                            (add_term_frees(tm,[]))
   766                                            (add_term_frees(tm,[]))
   767                             in fold_rev Forall vlist tm
   767                             in fold_rev Forall vlist tm
   768                             end
   768                             end
   769               (*--------------------------------------------------------------
   769               (*--------------------------------------------------------------
   779               val rcontext = rev cntxt
   779               val rcontext = rev cntxt
   780               val cncl = HOLogic.dest_Trueprop o Thm.prop_of
   780               val cncl = HOLogic.dest_Trueprop o Thm.prop_of
   781               val antl = case rcontext of [] => []
   781               val antl = case rcontext of [] => []
   782                          | _   => [S.list_mk_conj(map cncl rcontext)]
   782                          | _   => [S.list_mk_conj(map cncl rcontext)]
   783               val TC = genl(S.list_mk_imp(antl, A))
   783               val TC = genl(S.list_mk_imp(antl, A))
   784               val dummy = print_cterms "func:" [cterm_of sign func]
   784               val dummy = print_cterms "func:" [cterm_of thy func]
   785               val dummy = print_cterms "TC:"
   785               val dummy = print_cterms "TC:"
   786                               [cterm_of sign (HOLogic.mk_Trueprop TC)]
   786                               [cterm_of thy (HOLogic.mk_Trueprop TC)]
   787               val dummy = tc_list := (TC :: !tc_list)
   787               val dummy = tc_list := (TC :: !tc_list)
   788               val nestedp = isSome (S.find_term is_func TC)
   788               val nestedp = isSome (S.find_term is_func TC)
   789               val dummy = if nestedp then say "nested" else say "not_nested"
   789               val dummy = if nestedp then say "nested" else say "not_nested"
   790               val dummy = term_ref := ([func,TC]@(!term_ref))
   790               val dummy = term_ref := ([func,TC]@(!term_ref))
   791               val th' = if nestedp then raise RULES_ERR "solver" "nested function"
   791               val th' = if nestedp then raise RULES_ERR "solver" "nested function"
   792                         else let val cTC = cterm_of sign
   792                         else let val cTC = cterm_of thy
   793                                               (HOLogic.mk_Trueprop TC)
   793                                               (HOLogic.mk_Trueprop TC)
   794                              in case rcontext of
   794                              in case rcontext of
   795                                 [] => SPEC_ALL(ASSUME cTC)
   795                                 [] => SPEC_ALL(ASSUME cTC)
   796                                | _ => MP (SPEC_ALL (ASSUME cTC))
   796                                | _ => MP (SPEC_ALL (ASSUME cTC))
   797                                          (LIST_CONJ rcontext)
   797                                          (LIST_CONJ rcontext)