src/HOL/Nominal/nominal_permeq.ML
changeset 32960 69916a850301
parent 32733 71618deaf777
child 33244 db230399f890
equal deleted inserted replaced
32959:23a8c5ac35f8 32960:69916a850301
     1 (*  Title:      HOL/Nominal/nominal_permeq.ML
     1 (*  Title:      HOL/Nominal/nominal_permeq.ML
     2     Authors:    Christian Urban, Julien Narboux, TU Muenchen
     2     Author:     Christian Urban, TU Muenchen
     3 
     3     Author:     Julien Narboux, TU Muenchen
     4 Methods for simplifying permutations and
     4 
     5 for analysing equations involving permutations.
     5 Methods for simplifying permutations and for analysing equations
       
     6 involving permutations. 
     6 *)
     7 *)
     7 
     8 
     8 (*
     9 (*
     9 FIXMES:
    10 FIXMES:
    10 
    11 
    97   let 
    98   let 
    98     (* the "application" case is only applicable when the head of f is not a *)
    99     (* the "application" case is only applicable when the head of f is not a *)
    99     (* constant or when (f x) is a permuation with two or more arguments     *)
   100     (* constant or when (f x) is a permuation with two or more arguments     *)
   100     fun applicable_app t = 
   101     fun applicable_app t = 
   101           (case (strip_comb t) of
   102           (case (strip_comb t) of
   102 	      (Const ("Nominal.perm",_),ts) => (length ts) >= 2
   103               (Const ("Nominal.perm",_),ts) => (length ts) >= 2
   103             | (Const _,_) => false
   104             | (Const _,_) => false
   104             | _ => true)
   105             | _ => true)
   105   in
   106   in
   106     case redex of 
   107     case redex of 
   107         (* case pi o (f x) == (pi o f) (pi o x)          *)
   108         (* case pi o (f x) == (pi o f) (pi o x)          *)
   124 fun perm_simproc_fun' sg ss redex = 
   125 fun perm_simproc_fun' sg ss redex = 
   125    let 
   126    let 
   126      fun applicable_fun t =
   127      fun applicable_fun t =
   127        (case (strip_comb t) of
   128        (case (strip_comb t) of
   128           (Abs _ ,[]) => true
   129           (Abs _ ,[]) => true
   129 	| (Const ("Nominal.perm",_),_) => false
   130         | (Const ("Nominal.perm",_),_) => false
   130         | (Const _, _) => true
   131         | (Const _, _) => true
   131 	| _ => false)
   132         | _ => false)
   132    in
   133    in
   133      case redex of 
   134      case redex of 
   134        (* case pi o f == (%x. pi o (f ((rev pi)o x))) *)     
   135        (* case pi o f == (%x. pi o (f ((rev pi)o x))) *)     
   135        (Const("Nominal.perm",_) $ pi $ f)  => 
   136        (Const("Nominal.perm",_) $ pi $ f)  => 
   136           (if (applicable_fun f) then SOME (perm_fun_def) else NONE)
   137           (if (applicable_fun f) then SOME (perm_fun_def) else NONE)
   157 
   158 
   158 (* general simplification of permutations and permutation that arose from eqvt-problems *)
   159 (* general simplification of permutations and permutation that arose from eqvt-problems *)
   159 fun perm_simp stac ss = 
   160 fun perm_simp stac ss = 
   160     let val simps = ["perm_swap","perm_fresh_fresh","perm_bij","perm_pi_simp","swap_simps"]
   161     let val simps = ["perm_swap","perm_fresh_fresh","perm_bij","perm_pi_simp","swap_simps"]
   161     in 
   162     in 
   162 	perm_simp_gen stac simps [] ss
   163         perm_simp_gen stac simps [] ss
   163     end;
   164     end;
   164 
   165 
   165 fun eqvt_simp stac ss = 
   166 fun eqvt_simp stac ss = 
   166     let val simps = ["perm_swap","perm_fresh_fresh","perm_pi_simp"]
   167     let val simps = ["perm_swap","perm_fresh_fresh","perm_pi_simp"]
   167 	val eqvts_thms = NominalThmDecls.get_eqvt_thms (Simplifier.the_context ss);
   168         val eqvts_thms = NominalThmDecls.get_eqvt_thms (Simplifier.the_context ss);
   168     in 
   169     in 
   169 	perm_simp_gen stac simps eqvts_thms ss
   170         perm_simp_gen stac simps eqvts_thms ss
   170     end;
   171     end;
   171 
   172 
   172 
   173 
   173 (* main simplification tactics for permutations *)
   174 (* main simplification tactics for permutations *)
   174 fun perm_simp_tac_gen_i stac tactical ss i = DETERM (tactical (perm_simp stac ss i));
   175 fun perm_simp_tac_gen_i stac tactical ss i = DETERM (tactical (perm_simp stac ss i));
   250 (* to decide equation that come from support problems             *)
   251 (* to decide equation that come from support problems             *)
   251 (* since it contains looping rules the "recursion" - depth is set *)
   252 (* since it contains looping rules the "recursion" - depth is set *)
   252 (* to 10 - this seems to be sufficient in most cases              *)
   253 (* to 10 - this seems to be sufficient in most cases              *)
   253 fun perm_extend_simp_tac_i tactical ss =
   254 fun perm_extend_simp_tac_i tactical ss =
   254   let fun perm_extend_simp_tac_aux tactical ss n = 
   255   let fun perm_extend_simp_tac_aux tactical ss n = 
   255 	  if n=0 then K all_tac
   256           if n=0 then K all_tac
   256 	  else DETERM o 
   257           else DETERM o 
   257 	       (FIRST'[fn i => tactical ("splitting conjunctions on the rhs", rtac conjI i),
   258                (FIRST'[fn i => tactical ("splitting conjunctions on the rhs", rtac conjI i),
   258                        fn i => tactical (perm_simp asm_full_simp_tac ss i),
   259                        fn i => tactical (perm_simp asm_full_simp_tac ss i),
   259 		       fn i => tactical (perm_compose_tac ss i),
   260                        fn i => tactical (perm_compose_tac ss i),
   260 		       fn i => tactical (apply_cong_tac i), 
   261                        fn i => tactical (apply_cong_tac i), 
   261                        fn i => tactical (unfold_perm_fun_def_tac i),
   262                        fn i => tactical (unfold_perm_fun_def_tac i),
   262                        fn i => tactical (ext_fun_tac i)]
   263                        fn i => tactical (ext_fun_tac i)]
   263 		      THEN_ALL_NEW (TRY o (perm_extend_simp_tac_aux tactical ss (n-1))))
   264                       THEN_ALL_NEW (TRY o (perm_extend_simp_tac_aux tactical ss (n-1))))
   264   in perm_extend_simp_tac_aux tactical ss 10 end;
   265   in perm_extend_simp_tac_aux tactical ss 10 end;
   265 
   266 
   266 
   267 
   267 (* tactic that tries to solve "supports"-goals; first it *)
   268 (* tactic that tries to solve "supports"-goals; first it *)
   268 (* unfolds the support definition and strips off the     *)
   269 (* unfolds the support definition and strips off the     *)
   327 (* tactic that guesses whether an atom is fresh for an expression  *)
   328 (* tactic that guesses whether an atom is fresh for an expression  *)
   328 (* it first collects all free variables and tries to show that the *) 
   329 (* it first collects all free variables and tries to show that the *) 
   329 (* support of these free variables (op supports) the goal          *)
   330 (* support of these free variables (op supports) the goal          *)
   330 fun fresh_guess_tac_i tactical ss i st =
   331 fun fresh_guess_tac_i tactical ss i st =
   331     let 
   332     let 
   332 	val goal = List.nth(cprems_of st, i-1)
   333         val goal = List.nth(cprems_of st, i-1)
   333         val fin_supp = dynamic_thms st ("fin_supp")
   334         val fin_supp = dynamic_thms st ("fin_supp")
   334         val fresh_atm = dynamic_thms st ("fresh_atm")
   335         val fresh_atm = dynamic_thms st ("fresh_atm")
   335 	val ss1 = ss addsimps [symmetric fresh_def,fresh_prod,fresh_unit,conj_absorb,not_false]@fresh_atm
   336         val ss1 = ss addsimps [symmetric fresh_def,fresh_prod,fresh_unit,conj_absorb,not_false]@fresh_atm
   336         val ss2 = ss addsimps [supp_prod,supp_unit,finite_Un,finite_emptyI,conj_absorb]@fin_supp
   337         val ss2 = ss addsimps [supp_prod,supp_unit,finite_Un,finite_emptyI,conj_absorb]@fin_supp
   337     in
   338     in
   338       case Logic.strip_assums_concl (term_of goal) of
   339       case Logic.strip_assums_concl (term_of goal) of
   339           _ $ (Const ("Nominal.fresh", Type ("fun", [T, _])) $ _ $ t) => 
   340           _ $ (Const ("Nominal.fresh", Type ("fun", [T, _])) $ _ $ t) => 
   340           let
   341           let