src/HOL/Tools/Function/pat_completeness.ML
changeset 51717 9e7d1c139569
parent 47432 e1576d13e933
child 52467 24c6ddb48cb8
equal deleted inserted replaced
51709:19b47bfac6ef 51717:9e7d1c139569
     5 *)
     5 *)
     6 
     6 
     7 signature PAT_COMPLETENESS =
     7 signature PAT_COMPLETENESS =
     8 sig
     8 sig
     9     val pat_completeness_tac: Proof.context -> int -> tactic
     9     val pat_completeness_tac: Proof.context -> int -> tactic
    10     val prove_completeness : theory -> term list -> term -> term list list ->
    10     val prove_completeness : Proof.context -> term list -> term -> term list list ->
    11       term list list -> thm
    11       term list list -> thm
    12 end
    12 end
    13 
    13 
    14 structure Pat_Completeness : PAT_COMPLETENESS =
    14 structure Pat_Completeness : PAT_COMPLETENESS =
    15 struct
    15 struct
    59           Envir.subst_term_types (Sign.typ_match thy (body_type CT, T) Vartab.empty) (Const (Cn, CT)))
    59           Envir.subst_term_types (Sign.typ_match thy (body_type CT, T) Vartab.empty) (Const (Cn, CT)))
    60       (the (Datatype.get_constrs thy name))
    60       (the (Datatype.get_constrs thy name))
    61   | inst_constrs_of thy _ = raise Match
    61   | inst_constrs_of thy _ = raise Match
    62 
    62 
    63 
    63 
    64 fun transform_pat thy avars c_assum ([] , thm) = raise Match
    64 fun transform_pat _ avars c_assum ([] , thm) = raise Match
    65   | transform_pat thy avars c_assum (pat :: pats, thm) =
    65   | transform_pat ctxt avars c_assum (pat :: pats, thm) =
    66   let
    66   let
       
    67     val thy = Proof_Context.theory_of ctxt
    67     val (_, subps) = strip_comb pat
    68     val (_, subps) = strip_comb pat
    68     val eqs = map (cterm_of thy o HOLogic.mk_Trueprop o HOLogic.mk_eq) (avars ~~ subps)
    69     val eqs = map (cterm_of thy o HOLogic.mk_Trueprop o HOLogic.mk_eq) (avars ~~ subps)
    69     val c_eq_pat = simplify (HOL_basic_ss addsimps (map Thm.assume eqs)) c_assum
    70     val c_eq_pat = simplify (put_simpset HOL_basic_ss ctxt addsimps (map Thm.assume eqs)) c_assum
    70   in
    71   in
    71     (subps @ pats,
    72     (subps @ pats,
    72      fold_rev Thm.implies_intr eqs (Thm.implies_elim thm c_eq_pat))
    73      fold_rev Thm.implies_intr eqs (Thm.implies_elim thm c_eq_pat))
    73   end
    74   end
    74 
    75 
    75 
    76 
    76 exception COMPLETENESS
    77 exception COMPLETENESS
    77 
    78 
    78 fun constr_case thy P idx (v :: vs) pats cons =
    79 fun constr_case ctxt P idx (v :: vs) pats cons =
    79   let
    80   let
       
    81     val thy = Proof_Context.theory_of ctxt
    80     val (avars, pvars, newidx) = invent_vars cons idx
    82     val (avars, pvars, newidx) = invent_vars cons idx
    81     val c_hyp = cterm_of thy (HOLogic.mk_Trueprop (HOLogic.mk_eq (v, list_comb (cons, avars))))
    83     val c_hyp = cterm_of thy (HOLogic.mk_Trueprop (HOLogic.mk_eq (v, list_comb (cons, avars))))
    82     val c_assum = Thm.assume c_hyp
    84     val c_assum = Thm.assume c_hyp
    83     val newpats = map (transform_pat thy avars c_assum) (filter_pats thy cons pvars pats)
    85     val newpats = map (transform_pat ctxt avars c_assum) (filter_pats thy cons pvars pats)
    84   in
    86   in
    85     o_alg thy P newidx (avars @ vs) newpats
    87     o_alg ctxt P newidx (avars @ vs) newpats
    86     |> Thm.implies_intr c_hyp
    88     |> Thm.implies_intr c_hyp
    87     |> fold_rev (Thm.forall_intr o cterm_of thy) avars
    89     |> fold_rev (Thm.forall_intr o cterm_of thy) avars
    88   end
    90   end
    89   | constr_case _ _ _ _ _ _ = raise Match
    91   | constr_case _ _ _ _ _ _ = raise Match
    90 and o_alg thy P idx [] (([], Pthm) :: _)  = Pthm
    92 and o_alg _ P idx [] (([], Pthm) :: _)  = Pthm
    91   | o_alg thy P idx (v :: vs) [] = raise COMPLETENESS
    93   | o_alg _ P idx (v :: vs) [] = raise COMPLETENESS
    92   | o_alg thy P idx (v :: vs) pts =
    94   | o_alg ctxt P idx (v :: vs) pts =
    93   if forall (is_Free o hd o fst) pts (* Var case *)
    95   if forall (is_Free o hd o fst) pts (* Var case *)
    94   then o_alg thy P idx vs
    96   then o_alg ctxt P idx vs
    95          (map (fn (pv :: pats, thm) =>
    97          (map (fn (pv :: pats, thm) =>
    96            (pats, refl RS (inst_free (cterm_of thy pv) (cterm_of thy v) thm))) pts)
    98            (pats, refl RS
       
    99             (inst_free (cterm_of (Proof_Context.theory_of ctxt) pv)
       
   100               (cterm_of (Proof_Context.theory_of ctxt) v) thm))) pts)
    97   else (* Cons case *)
   101   else (* Cons case *)
    98     let
   102     let
       
   103       val thy = Proof_Context.theory_of ctxt
    99       val T = fastype_of v
   104       val T = fastype_of v
   100       val (tname, _) = dest_Type T
   105       val (tname, _) = dest_Type T
   101       val {exhaust=case_thm, ...} = Datatype.the_info thy tname
   106       val {exhaust=case_thm, ...} = Datatype.the_info thy tname
   102       val constrs = inst_constrs_of thy T
   107       val constrs = inst_constrs_of thy T
   103       val c_cases = map (constr_case thy P idx (v :: vs) pts) constrs
   108       val c_cases = map (constr_case ctxt P idx (v :: vs) pts) constrs
   104     in
   109     in
   105       inst_case_thm thy v P case_thm
   110       inst_case_thm thy v P case_thm
   106       |> fold (curry op COMP) c_cases
   111       |> fold (curry op COMP) c_cases
   107     end
   112     end
   108   | o_alg _ _ _ _ _ = raise Match
   113   | o_alg _ _ _ _ _ = raise Match
   109 
   114 
   110 fun prove_completeness thy xs P qss patss =
   115 fun prove_completeness ctxt xs P qss patss =
   111   let
   116   let
       
   117     val thy = Proof_Context.theory_of ctxt
   112     fun mk_assum qs pats =
   118     fun mk_assum qs pats =
   113       HOLogic.mk_Trueprop P
   119       HOLogic.mk_Trueprop P
   114       |> fold_rev (curry Logic.mk_implies o HOLogic.mk_Trueprop o HOLogic.mk_eq) (xs ~~ pats)
   120       |> fold_rev (curry Logic.mk_implies o HOLogic.mk_Trueprop o HOLogic.mk_eq) (xs ~~ pats)
   115       |> fold_rev Logic.all qs
   121       |> fold_rev Logic.all qs
   116       |> cterm_of thy
   122       |> cterm_of thy
   117 
   123 
   118     val hyps = map2 mk_assum qss patss
   124     val hyps = map2 mk_assum qss patss
   119     fun inst_hyps hyp qs = fold (Thm.forall_elim o cterm_of thy) qs (Thm.assume hyp)
   125     fun inst_hyps hyp qs = fold (Thm.forall_elim o cterm_of thy) qs (Thm.assume hyp)
   120     val assums = map2 inst_hyps hyps qss
   126     val assums = map2 inst_hyps hyps qss
   121     in
   127     in
   122       o_alg thy P 2 xs (patss ~~ assums)
   128       o_alg ctxt P 2 xs (patss ~~ assums)
   123       |> fold_rev Thm.implies_intr hyps
   129       |> fold_rev Thm.implies_intr hyps
   124     end
   130     end
   125 
   131 
   126 fun pat_completeness_tac ctxt = SUBGOAL (fn (subgoal, i) =>
   132 fun pat_completeness_tac ctxt = SUBGOAL (fn (subgoal, i) =>
   127   let
   133   let
   141     val (qss, x_pats) = split_list (map pat_of cases)
   147     val (qss, x_pats) = split_list (map pat_of cases)
   142     val xs = map fst (hd x_pats)
   148     val xs = map fst (hd x_pats)
   143       handle List.Empty => raise COMPLETENESS
   149       handle List.Empty => raise COMPLETENESS
   144 
   150 
   145     val patss = map (map snd) x_pats
   151     val patss = map (map snd) x_pats
   146     val complete_thm = prove_completeness thy xs thesis qss patss
   152     val complete_thm = prove_completeness ctxt xs thesis qss patss
   147       |> fold_rev (Thm.forall_intr o cterm_of thy) vs
   153       |> fold_rev (Thm.forall_intr o cterm_of thy) vs
   148     in
   154     in
   149       PRIMITIVE (fn st => Drule.compose_single(complete_thm, i, st))
   155       PRIMITIVE (fn st => Drule.compose_single(complete_thm, i, st))
   150   end
   156   end
   151   handle COMPLETENESS => no_tac)
   157   handle COMPLETENESS => no_tac)