src/HOL/Tools/Function/lexicographic_order.ML
changeset 56231 b98813774a63
parent 51958 bca32217b304
child 57959 1bfed12a7646
equal deleted inserted replaced
56230:3e449273942a 56231:b98813774a63
   172     ["", "Could not find lexicographic termination order."])
   172     ["", "Could not find lexicographic termination order."])
   173   end
   173   end
   174 
   174 
   175 (** The Main Function **)
   175 (** The Main Function **)
   176 
   176 
   177 fun lex_order_tac quiet ctxt solve_tac (st: thm) =
   177 fun lex_order_tac quiet ctxt solve_tac st = SUBGOAL (fn _ =>
   178   let
   178   let
   179     val thy = Proof_Context.theory_of ctxt
   179     val thy = Proof_Context.theory_of ctxt
   180     val ((_ $ (_ $ rel)) :: tl) = prems_of st
   180     val ((_ $ (_ $ rel)) :: tl) = prems_of st
   181 
   181 
   182     val (domT, _) = HOLogic.dest_prodT (HOLogic.dest_setT (fastype_of rel))
   182     val (domT, _) = HOLogic.dest_prodT (HOLogic.dest_setT (fastype_of rel))
   185       MeasureFunctions.get_measure_functions ctxt domT
   185       MeasureFunctions.get_measure_functions ctxt domT
   186 
   186 
   187     val table = (* 2: create table *)
   187     val table = (* 2: create table *)
   188       map (fn t => map (mk_cell thy solve_tac (dest_term t)) measure_funs) tl
   188       map (fn t => map (mk_cell thy solve_tac (dest_term t)) measure_funs) tl
   189   in
   189   in
   190     case search_table table of
   190     fn st =>
   191       NONE => if quiet then no_tac st else error (no_order_msg ctxt table tl measure_funs)
   191       case search_table table of
   192     | SOME order =>
   192         NONE => if quiet then no_tac st else error (no_order_msg ctxt table tl measure_funs)
   193       let
   193       | SOME order =>
   194         val clean_table = map (fn x => map (nth x) order) table
   194         let
   195         val relation = mk_measures domT (map (nth measure_funs) order)
   195           val clean_table = map (fn x => map (nth x) order) table
   196         val _ =
   196           val relation = mk_measures domT (map (nth measure_funs) order)
   197           if not quiet then
   197           val _ =
   198             Pretty.writeln (Pretty.block
   198             if not quiet then
   199               [Pretty.str "Found termination order:", Pretty.brk 1,
   199               Pretty.writeln (Pretty.block
   200                 Pretty.quote (Syntax.pretty_term ctxt relation)])
   200                 [Pretty.str "Found termination order:", Pretty.brk 1,
   201           else ()
   201                   Pretty.quote (Syntax.pretty_term ctxt relation)])
   202 
   202             else ()
   203       in (* 4: proof reconstruction *)
   203   
   204         st |> (PRIMITIVE (cterm_instantiate [(cterm_of thy rel, cterm_of thy relation)])
   204         in (* 4: proof reconstruction *)
   205         THEN (REPEAT (rtac @{thm "wf_mlex"} 1))
   205           st |> (PRIMITIVE (cterm_instantiate [(cterm_of thy rel, cterm_of thy relation)])
   206         THEN (rtac @{thm "wf_empty"} 1)
   206           THEN (REPEAT (rtac @{thm "wf_mlex"} 1))
   207         THEN EVERY (map prove_row clean_table))
   207           THEN (rtac @{thm "wf_empty"} 1)
   208       end
   208           THEN EVERY (map prove_row clean_table))
   209   end
   209         end
       
   210   end) 1 st;
   210 
   211 
   211 fun lexicographic_order_tac quiet ctxt =
   212 fun lexicographic_order_tac quiet ctxt =
   212   TRY (Function_Common.apply_termination_rule ctxt 1) THEN
   213   TRY (Function_Common.apply_termination_rule ctxt 1) THEN
   213   lex_order_tac quiet ctxt
   214   lex_order_tac quiet ctxt
   214     (auto_tac (ctxt addsimps Function_Common.Termination_Simps.get ctxt))
   215     (auto_tac (ctxt addsimps Function_Common.Termination_Simps.get ctxt))