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 |