src/HOL/Tools/Function/termination.ML
changeset 32602 f2b741473860
parent 32149 ef59550a55d3
child 32683 7c1fe854ca6a
equal deleted inserted replaced
32601:47d0c967c64e 32602:f2b741473860
    77           in dest s l @ dest t r end
    77           in dest s l @ dest t r end
    78   in dest end
    78   in dest end
    79 
    79 
    80 
    80 
    81 (* concrete versions for sum types *)
    81 (* concrete versions for sum types *)
    82 fun is_inj (Const ("Sum_Type.Inl", _) $ _) = true
    82 fun is_inj (Const (@{const_name Sum_Type.Inl}, _) $ _) = true
    83   | is_inj (Const ("Sum_Type.Inr", _) $ _) = true
    83   | is_inj (Const (@{const_name Sum_Type.Inr}, _) $ _) = true
    84   | is_inj _ = false
    84   | is_inj _ = false
    85 
    85 
    86 fun dest_inl (Const ("Sum_Type.Inl", _) $ t) = SOME t
    86 fun dest_inl (Const (@{const_name Sum_Type.Inl}, _) $ t) = SOME t
    87   | dest_inl _ = NONE
    87   | dest_inl _ = NONE
    88 
    88 
    89 fun dest_inr (Const ("Sum_Type.Inr", _) $ t) = SOME t
    89 fun dest_inr (Const (@{const_name Sum_Type.Inr}, _) $ t) = SOME t
    90   | dest_inr _ = NONE
    90   | dest_inr _ = NONE
    91 
    91 
    92 
    92 
    93 fun mk_skel ps =
    93 fun mk_skel ps =
    94   let
    94   let
   143           sk
   143           sk
   144   |> fst
   144   |> fst
   145 
   145 
   146 fun mk_sum_skel rel =
   146 fun mk_sum_skel rel =
   147   let
   147   let
   148     val cs = FundefLib.dest_binop_list @{const_name union} rel
   148     val cs = FundefLib.dest_binop_list @{const_name Set.union} rel
   149     fun collect_pats (Const ("Collect", _) $ Abs (_, _, c)) =
   149     fun collect_pats (Const (@{const_name Collect}, _) $ Abs (_, _, c)) =
   150       let
   150       let
   151         val (Const ("op &", _) $ (Const ("op =", _) $ _ $ (Const ("Pair", _) $ r $ l)) $ Gam)
   151         val (Const ("op &", _) $ (Const ("op =", _) $ _ $ (Const ("Pair", _) $ r $ l)) $ Gam)
   152           = Term.strip_qnt_body "Ex" c
   152           = Term.strip_qnt_body "Ex" c
   153       in cons r o cons l end
   153       in cons r o cons l end
   154   in
   154   in
   177   Term2tab.lookup C (c1, c2)
   177   Term2tab.lookup C (c1, c2)
   178 
   178 
   179 fun get_descent (_, _, _, _, D) c m1 m2 =
   179 fun get_descent (_, _, _, _, D) c m1 m2 =
   180   Term3tab.lookup D (c, (m1, m2))
   180   Term3tab.lookup D (c, (m1, m2))
   181 
   181 
   182 fun dest_call D (Const ("Collect", _) $ Abs (_, _, c)) =
   182 fun dest_call D (Const (@{const_name Collect}, _) $ Abs (_, _, c)) =
   183   let
   183   let
   184     val n = get_num_points D
   184     val n = get_num_points D
   185     val (sk, _, _, _, _) = D
   185     val (sk, _, _, _, _) = D
   186     val vs = Term.strip_qnt_vars "Ex" c
   186     val vs = Term.strip_qnt_vars "Ex" c
   187 
   187 
   231   end
   231   end
   232 
   232 
   233 fun CALLS tac i st =
   233 fun CALLS tac i st =
   234   if Thm.no_prems st then all_tac st
   234   if Thm.no_prems st then all_tac st
   235   else case Thm.term_of (Thm.cprem_of st i) of
   235   else case Thm.term_of (Thm.cprem_of st i) of
   236     (_ $ (_ $ rel)) => tac (FundefLib.dest_binop_list @{const_name union} rel, i) st
   236     (_ $ (_ $ rel)) => tac (FundefLib.dest_binop_list @{const_name Set.union} rel, i) st
   237   |_ => no_tac st
   237   |_ => no_tac st
   238 
   238 
   239 type ttac = (data -> int -> tactic) -> (data -> int -> tactic) -> data -> int -> tactic
   239 type ttac = (data -> int -> tactic) -> (data -> int -> tactic) -> data -> int -> tactic
   240 
   240 
   241 fun TERMINATION ctxt tac =
   241 fun TERMINATION ctxt tac =
   242   SUBGOAL (fn (_ $ (Const (@{const_name "wf"}, wfT) $ rel), i) =>
   242   SUBGOAL (fn (_ $ (Const (@{const_name wf}, wfT) $ rel), i) =>
   243   let
   243   let
   244     val (T, _) = HOLogic.dest_prodT (HOLogic.dest_setT (domain_type wfT))
   244     val (T, _) = HOLogic.dest_prodT (HOLogic.dest_setT (domain_type wfT))
   245   in
   245   in
   246     tac (create ctxt T rel) i
   246     tac (create ctxt T rel) i
   247   end)
   247   end)
   291 
   291 
   292       val relation =
   292       val relation =
   293           if null ineqs then
   293           if null ineqs then
   294               Const (@{const_name Set.empty}, fastype_of rel)
   294               Const (@{const_name Set.empty}, fastype_of rel)
   295           else
   295           else
   296               foldr1 (HOLogic.mk_binop @{const_name union}) (map mk_compr ineqs)
   296               foldr1 (HOLogic.mk_binop @{const_name Set.union}) (map mk_compr ineqs)
   297 
   297 
   298       fun solve_membership_tac i =
   298       fun solve_membership_tac i =
   299           (EVERY' (replicate (i - 2) (rtac @{thm UnI2}))  (* pick the right component of the union *)
   299           (EVERY' (replicate (i - 2) (rtac @{thm UnI2}))  (* pick the right component of the union *)
   300           THEN' (fn j => TRY (rtac @{thm UnI1} j))
   300           THEN' (fn j => TRY (rtac @{thm UnI1} j))
   301           THEN' (rtac @{thm CollectI})                    (* unfold comprehension *)
   301           THEN' (rtac @{thm CollectI})                    (* unfold comprehension *)