src/HOL/Tools/Function/termination.ML
changeset 67149 e61557884799
parent 60784 4f590c08fd5d
child 79971 033f90dc441d
equal deleted inserted replaced
67148:d24dcac5eb4c 67149:e61557884799
    65           in dest s l @ dest t r end
    65           in dest s l @ dest t r end
    66   in dest end
    66   in dest end
    67 
    67 
    68 
    68 
    69 (* concrete versions for sum types *)
    69 (* concrete versions for sum types *)
    70 fun is_inj (Const (@{const_name Sum_Type.Inl}, _) $ _) = true
    70 fun is_inj (Const (\<^const_name>\<open>Sum_Type.Inl\<close>, _) $ _) = true
    71   | is_inj (Const (@{const_name Sum_Type.Inr}, _) $ _) = true
    71   | is_inj (Const (\<^const_name>\<open>Sum_Type.Inr\<close>, _) $ _) = true
    72   | is_inj _ = false
    72   | is_inj _ = false
    73 
    73 
    74 fun dest_inl (Const (@{const_name Sum_Type.Inl}, _) $ t) = SOME t
    74 fun dest_inl (Const (\<^const_name>\<open>Sum_Type.Inl\<close>, _) $ t) = SOME t
    75   | dest_inl _ = NONE
    75   | dest_inl _ = NONE
    76 
    76 
    77 fun dest_inr (Const (@{const_name Sum_Type.Inr}, _) $ t) = SOME t
    77 fun dest_inr (Const (\<^const_name>\<open>Sum_Type.Inr\<close>, _) $ t) = SOME t
    78   | dest_inr _ = NONE
    78   | dest_inr _ = NONE
    79 
    79 
    80 
    80 
    81 fun mk_skel ps =
    81 fun mk_skel ps =
    82   let
    82   let
    90   in
    90   in
    91     snd (skel 0 ps)
    91     snd (skel 0 ps)
    92   end
    92   end
    93 
    93 
    94 (* compute list of types for nodes *)
    94 (* compute list of types for nodes *)
    95 fun node_types sk T = dest_tree (fn Type (@{type_name Sum_Type.sum}, [LT, RT]) => (LT, RT)) sk T |> map snd
    95 fun node_types sk T = dest_tree (fn Type (\<^type_name>\<open>Sum_Type.sum\<close>, [LT, RT]) => (LT, RT)) sk T |> map snd
    96 
    96 
    97 (* find index and raw term *)
    97 (* find index and raw term *)
    98 fun dest_inj (SLeaf i) trm = (i, trm)
    98 fun dest_inj (SLeaf i) trm = (i, trm)
    99   | dest_inj (SBranch (s, t)) trm =
    99   | dest_inj (SBranch (s, t)) trm =
   100     case dest_inl trm of
   100     case dest_inl trm of
   123           sk
   123           sk
   124   |> fst
   124   |> fst
   125 
   125 
   126 fun mk_sum_skel rel =
   126 fun mk_sum_skel rel =
   127   let
   127   let
   128     val cs = Function_Lib.dest_binop_list @{const_name Lattices.sup} rel
   128     val cs = Function_Lib.dest_binop_list \<^const_name>\<open>Lattices.sup\<close> rel
   129     fun collect_pats (Const (@{const_name Collect}, _) $ Abs (_, _, c)) =
   129     fun collect_pats (Const (\<^const_name>\<open>Collect\<close>, _) $ Abs (_, _, c)) =
   130       let
   130       let
   131         val (Const (@{const_name HOL.conj}, _) $ (Const (@{const_name HOL.eq}, _) $ _ $ (Const (@{const_name Pair}, _) $ r $ l)) $ _)
   131         val (Const (\<^const_name>\<open>HOL.conj\<close>, _) $ (Const (\<^const_name>\<open>HOL.eq\<close>, _) $ _ $ (Const (\<^const_name>\<open>Pair\<close>, _) $ r $ l)) $ _)
   132           = Term.strip_qnt_body @{const_name Ex} c
   132           = Term.strip_qnt_body \<^const_name>\<open>Ex\<close> c
   133       in cons r o cons l end
   133       in cons r o cons l end
   134   in
   134   in
   135     mk_skel (fold collect_pats cs [])
   135     mk_skel (fold collect_pats cs [])
   136   end
   136   end
   137 
   137 
   138 fun prove_chain ctxt chain_tac (c1, c2) =
   138 fun prove_chain ctxt chain_tac (c1, c2) =
   139   let
   139   let
   140     val goal =
   140     val goal =
   141       HOLogic.mk_eq (HOLogic.mk_binop @{const_name Relation.relcomp} (c1, c2),
   141       HOLogic.mk_eq (HOLogic.mk_binop \<^const_name>\<open>Relation.relcomp\<close> (c1, c2),
   142         Const (@{const_abbrev Set.empty}, fastype_of c1))
   142         Const (\<^const_abbrev>\<open>Set.empty\<close>, fastype_of c1))
   143       |> HOLogic.mk_Trueprop (* "C1 O C2 = {}" *)
   143       |> HOLogic.mk_Trueprop (* "C1 O C2 = {}" *)
   144   in
   144   in
   145     (case Function_Lib.try_proof ctxt (Thm.cterm_of ctxt goal) chain_tac of
   145     (case Function_Lib.try_proof ctxt (Thm.cterm_of ctxt goal) chain_tac of
   146       Function_Lib.Solved thm => SOME thm
   146       Function_Lib.Solved thm => SOME thm
   147     | _ => NONE)
   147     | _ => NONE)
   148   end
   148   end
   149 
   149 
   150 
   150 
   151 fun dest_call' sk (Const (@{const_name Collect}, _) $ Abs (_, _, c)) =
   151 fun dest_call' sk (Const (\<^const_name>\<open>Collect\<close>, _) $ Abs (_, _, c)) =
   152   let
   152   let
   153     val vs = Term.strip_qnt_vars @{const_name Ex} c
   153     val vs = Term.strip_qnt_vars \<^const_name>\<open>Ex\<close> c
   154 
   154 
   155     (* FIXME: throw error "dest_call" for malformed terms *)
   155     (* FIXME: throw error "dest_call" for malformed terms *)
   156     val (Const (@{const_name HOL.conj}, _) $ (Const (@{const_name HOL.eq}, _) $ _ $ (Const (@{const_name Pair}, _) $ r $ l)) $ Gam)
   156     val (Const (\<^const_name>\<open>HOL.conj\<close>, _) $ (Const (\<^const_name>\<open>HOL.eq\<close>, _) $ _ $ (Const (\<^const_name>\<open>Pair\<close>, _) $ r $ l)) $ Gam)
   157       = Term.strip_qnt_body @{const_name Ex} c
   157       = Term.strip_qnt_body \<^const_name>\<open>Ex\<close> c
   158     val (p, l') = dest_inj sk l
   158     val (p, l') = dest_inj sk l
   159     val (q, r') = dest_inj sk r
   159     val (q, r') = dest_inj sk r
   160   in
   160   in
   161     (vs, p, l', q, r', Gam)
   161     (vs, p, l', q, r', Gam)
   162   end
   162   end
   168   let
   168   let
   169     fun try rel =
   169     fun try rel =
   170       try_proof ctxt (Thm.cterm_of ctxt
   170       try_proof ctxt (Thm.cterm_of ctxt
   171         (Logic.list_all (vs,
   171         (Logic.list_all (vs,
   172            Logic.mk_implies (HOLogic.mk_Trueprop Gam,
   172            Logic.mk_implies (HOLogic.mk_Trueprop Gam,
   173              HOLogic.mk_Trueprop (Const (rel, @{typ "nat \<Rightarrow> nat \<Rightarrow> bool"})
   173              HOLogic.mk_Trueprop (Const (rel, \<^typ>\<open>nat \<Rightarrow> nat \<Rightarrow> bool\<close>)
   174                $ (m2 $ r) $ (m1 $ l)))))) tac
   174                $ (m2 $ r) $ (m1 $ l)))))) tac
   175   in
   175   in
   176     (case try @{const_name Orderings.less} of
   176     (case try \<^const_name>\<open>Orderings.less\<close> of
   177       Solved thm => Less thm
   177       Solved thm => Less thm
   178     | Stuck thm =>
   178     | Stuck thm =>
   179         (case try @{const_name Orderings.less_eq} of
   179         (case try \<^const_name>\<open>Orderings.less_eq\<close> of
   180           Solved thm2 => LessEq (thm2, thm)
   180           Solved thm2 => LessEq (thm2, thm)
   181         | Stuck thm2 =>
   181         | Stuck thm2 =>
   182             if Thm.prems_of thm2 = [HOLogic.Trueprop $ @{term False}]
   182             if Thm.prems_of thm2 = [HOLogic.Trueprop $ \<^term>\<open>False\<close>]
   183             then False thm2 else None (thm2, thm)
   183             then False thm2 else None (thm2, thm)
   184         | _ => raise Match) (* FIXME *)
   184         | _ => raise Match) (* FIXME *)
   185     | _ => raise Match)
   185     | _ => raise Match)
   186 end
   186 end
   187 
   187 
   223   SOME (D (c, (m1, m2)))
   223   SOME (D (c, (m1, m2)))
   224 
   224 
   225 fun CALLS tac i st =
   225 fun CALLS tac i st =
   226   if Thm.no_prems st then all_tac st
   226   if Thm.no_prems st then all_tac st
   227   else case Thm.term_of (Thm.cprem_of st i) of
   227   else case Thm.term_of (Thm.cprem_of st i) of
   228     (_ $ (_ $ rel)) => tac (Function_Lib.dest_binop_list @{const_name Lattices.sup} rel, i) st
   228     (_ $ (_ $ rel)) => tac (Function_Lib.dest_binop_list \<^const_name>\<open>Lattices.sup\<close> rel, i) st
   229   |_ => no_tac st
   229   |_ => no_tac st
   230 
   230 
   231 type ttac = data -> int -> tactic
   231 type ttac = data -> int -> tactic
   232 
   232 
   233 fun TERMINATION ctxt atac tac =
   233 fun TERMINATION ctxt atac tac =
   234   SUBGOAL (fn (_ $ (Const (@{const_name wf}, wfT) $ rel), i) =>
   234   SUBGOAL (fn (_ $ (Const (\<^const_name>\<open>wf\<close>, wfT) $ rel), i) =>
   235   let
   235   let
   236     val (T, _) = HOLogic.dest_prodT (HOLogic.dest_setT (domain_type wfT))
   236     val (T, _) = HOLogic.dest_prodT (HOLogic.dest_setT (domain_type wfT))
   237   in
   237   in
   238     tac (create ctxt atac atac T rel) i
   238     tac (create ctxt atac atac T rel) i
   239   end)
   239   end)
   256 fun mk_pair_compr (T, qs, l, r, conds) =
   256 fun mk_pair_compr (T, qs, l, r, conds) =
   257   let
   257   let
   258     val pT = HOLogic.mk_prodT (T, T)
   258     val pT = HOLogic.mk_prodT (T, T)
   259     val n = length qs
   259     val n = length qs
   260     val peq = HOLogic.eq_const pT $ Bound n $ (HOLogic.pair_const T T $ l $ r)
   260     val peq = HOLogic.eq_const pT $ Bound n $ (HOLogic.pair_const T T $ l $ r)
   261     val conds' = if null conds then [@{term True}] else conds
   261     val conds' = if null conds then [\<^term>\<open>True\<close>] else conds
   262   in
   262   in
   263     HOLogic.Collect_const pT $
   263     HOLogic.Collect_const pT $
   264     Abs ("uu_", pT,
   264     Abs ("uu_", pT,
   265       (foldr1 HOLogic.mk_conj (peq :: conds')
   265       (foldr1 HOLogic.mk_conj (peq :: conds')
   266       |> fold_rev (fn v => fn t => HOLogic.exists_const (fastype_of v) $ lambda v t) qs))
   266       |> fold_rev (fn v => fn t => HOLogic.exists_const (fastype_of v) $ lambda v t) qs))
   282         mk_pair_compr (fastype_of lhs, vars, lhs, rhs, map (Object_Logic.atomize_term ctxt) prems)
   282         mk_pair_compr (fastype_of lhs, vars, lhs, rhs, map (Object_Logic.atomize_term ctxt) prems)
   283       end
   283       end
   284 
   284 
   285     val relation =
   285     val relation =
   286       if null ineqs
   286       if null ineqs
   287       then Const (@{const_abbrev Set.empty}, fastype_of rel)
   287       then Const (\<^const_abbrev>\<open>Set.empty\<close>, fastype_of rel)
   288       else map mk_compr ineqs
   288       else map mk_compr ineqs
   289         |> foldr1 (HOLogic.mk_binop @{const_name Lattices.sup})
   289         |> foldr1 (HOLogic.mk_binop \<^const_name>\<open>Lattices.sup\<close>)
   290 
   290 
   291     fun solve_membership_tac i =
   291     fun solve_membership_tac i =
   292       (EVERY' (replicate (i - 2) (resolve_tac ctxt @{thms UnI2}))  (* pick the right component of the union *)
   292       (EVERY' (replicate (i - 2) (resolve_tac ctxt @{thms UnI2}))  (* pick the right component of the union *)
   293       THEN' (fn j => TRY (resolve_tac ctxt @{thms UnI1} j))
   293       THEN' (fn j => TRY (resolve_tac ctxt @{thms UnI1} j))
   294       THEN' (resolve_tac ctxt @{thms CollectI})                    (* unfold comprehension *)
   294       THEN' (resolve_tac ctxt @{thms CollectI})                    (* unfold comprehension *)